数论题，主要在于推演。
洛谷的《又是毕业季I》更好玩
发现对于所有的同学的能力值，只要我们选出每个数的所有因子并记录所有同学所有因子出现的次数，就可以得到一个
\(c\) 数组为所有因子出现的次数。
因为让输出 \(1\sim n\)
所有的值，而且因子数
c[k-1]>=c[k]，我们就一定可以从因子数最高的 \(c\) 向下遍历到 c[i]
更高的位置，即最大公约数i向下递减，当第一次发现
c[i]>=i，那么就肯定存在 >=i 个数的因子是
i，符合题意。
数论真有意思。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int c[1000005],n;
int main()
{
int t=0;
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
t=max(t,x);
int m=sqrt(x);
for(int j=1;j<=m;j++)
if(!(x%j))
{
c[j]++;
if(x!=j*j)c[x/j]++;
}
}
for(int i=1;i<=n;i++)
{
while(c[t]<i)t--;
cout<<t<<endl;
}
return 0;
}
|
